Developer CD Series 1992 June: ROMin Holiday

home *** CD-ROM | disk | FTP | other *** search

/ Developer CD Series 1992 June: ROMin Holiday / ADC Developer CD (1992-06) (''ROMin Holiday'')_iso / Developer Connection - 06-1992.iso / Development Platforms / LISP Related / U. Mass AI & LISP Tools / MODULES / DNET / DNET-Doc.text < prev next >

Wrap

Text File | 1990-06-22 | 18.4 KB | 427 lines | [TEXT/CCL ]

=========================================================================== About DNET -- Dan Suthers =========================================================================== ; ; USER'S DOCUMENTATION ; ; A discrimination net facility lets one do several things: ; ; - 'Uniquify' list expressions under EQ by allowing one to retrive a stored ; expression using an EQUAL expression as the key. ; - Associate properties with list expressions (using the above capability). ; - Ask whether a particular expression has been stored in a data base. ; - Retrieve expressions by pattern matching using variables in either the ; retrieval key or in the stored expressions. ; - Change contexts efficiently by changing the discrimination net in use. ; ; A discrimination net may be used to implement a simple data base, or to ; support more sophisticated systems for deductive retrieval, forward and ; backward chaining of rules, and/or truth maintenance. The present package ; attempts to be simple, general, and efficient by providing the most basic ; operations efficiently implemented without frills. ; ; Most operations take the discrimination net as their last argument. This ; facilitates context switching. Storage of dotted lists is not allowed, ; due to the indexing method used. Pattern matching retrieval processes ; variables in either the query pattern (MATCH-PATTERN) or the network ; (MATCH-EXPRESSION), or both (MATCH). The general MATCH function is less ; efficient, and most applications only need to match in one direction. ; ; When a new expression is added via INDEXPR, some applications will need ; to do special processing of the expression and/or its dnet-terminal. If ; this were left to the application after the INDEXPR call returned, this ; processing could not be done on expressions loaded from a file saved by ; SAVE-DNET, since the latter writes calls to INDEXPR with no surrounding ; application-specific forms. The solution is to have an INDEXPR-HOOK, ; which when non-nil is a lambda called on all newly indexed expressions ; and their dnet-terminals. There is also a corresponding DELEXPR-HOOK. ; ; Discrimination Net Operations: ; MAKE-DNET makes new ones. ; RESET-DNET resets to empty and modifies associated info. ; DNET-INFO associates information with a dnet. ; ALL-EXPRESSIONS returns all expressions in a dnet (slow). ; MAP-DNET-TERMINALS maps a function across all dnet-terminals in a dnet. ; DESTROY-DNET undefines and deallocates a dnet. ; SAVE-DNET saves a dnet to a file (slow). ; (Functions requiring retrieval of all expressions are slow because DNET is ; optimized for balancing fast access to single expressions with space economy.) ; ; Expression-Based Operations: ; These do not process variables (treat variables like any other atom). ; INDEXPR puts an expression in a dnet. ; GETEXPR retrieves an expression from a dnet. ; DELEXPR deletes an expression from a dnet. ; EXPR-INFO associates information with an expression in a dnet. ; ; Pattern-Based Operations: ; A pattern is a symbolic expression which may contain variables. ; Variables are symbols in the package ?. It is recommended that ; one declare all variables before use with the (defvariable <sym>) form. ; No symbol should ever be uninterned from ? by another program. ; DEFVARIABLE defines a variable. ; VARIABLE-P tests whether an object is a variable. ; PATTERN-P tests whether an object is an expression containing a variable. ; VARIABLES-IN-PATTERN returns a list of variables in a pattern. ; MATCH retrieves patterns (or expressions) matching a given pattern (expression). ; MATCH-PATTERN retrieves expressions matching a given pattern. ; MATCH-EXPRESSION retrieves patterns matching a given expression. ; BIND-VARS does the variable binding (restricted unification) for one-way ; match candidates, and is exported for its potential usefulness. ; UNIFY does bidirectional variable binding (for MATCH), and is exported. ; SUBSTITUTE-BINDINGS substitutes for variables in a pattern to give an ; expression, given a binding list. ; ; NOTE ON BEHAVIOR -- The following behavior is CORRECT: ; ; ? (dnet:make-dnet :test-dnet) ; ? (dnet:indexpr '(a b c) :test-dnet) ; ? (dnet:indexpr '(a ?:x c) :test-dnet) ; ? (dnet:indexpr '(a ?:y c) :test-dnet) ; ? (dnet:indexpr '(a (?:x y z) c) :test-dnet) ; ; ? (dnet:match-pattern '(a ?:x c) :test-dnet) ; ((A (?:X Y Z) C) (A ?:Y C) (A ?:X C) (A B C)) ; (((?:X ?:X Y Z)) ((?:X . ?:Y)) ((?:X . ?:X)) ((?:X . B))) ; ; ? (dnet:match-expression '(a ?:x c) :test-dnet) ; ((A ?:X C) (A ?:Y C)) ; (((?:X . ?:X)) ((?:Y . ?:X))) ; ; ? (dnet:match '(a ?:x c) :test-dnet) ; ((A ?:Y C) (A ?:X C) (A B C)) ; (((?:X . ?:Y)) NIL ((?:X . B))) ; (NIL NIL NIL) ; ; MATCH-PATTERN ignores variables in the DNET. Thus, (?:X Y Z) is a ; constant list as far as it is concerned, and there is no contradiction ; to binding ?:X to (?:X Y Z). This feature may be useful when trying ; to retrieve patterns without processing their variables. ; MATCH-EXPRESSION treats the ?:x in the query as a constant, so only ; returns the patterns in the DNET which match it. One happens to have ; a variable which is the same as the constant; the other matches the ; variable ?:y in DNET to the constant ?:x. ; MATCH will only return patterns which logically unify with the query ; pattern. Thus, it is correctly more restrictive than MATCH-PATTERN ; above, as ?:X cannot be bound to an expression containing itself. ; While MATCH returns bindings in both directions (the second and third ; values), (?:Y . ?:X) does not appear in the second binding list for ; (A ?:Y C) because (?:X . ?:Y) already expressed the binding, "using ; up" ?:Y. I.e., there is no redundancy across the binding lists. --------------------------------------------------------------------------- Documentation for Exported Symbols in Package DNET (generated by PDOC): --------------------------------------------------------------------------- *?-PACKAGE* Exported but undocumented Variable. *DNET-PACKAGE* Exported but undocumented Variable. ALL-EXPRESSIONS Function: all-expressions <dnet> [Function] Returns a list of all expressions in the indicated <dnet>. The outer list is constructed fresh and may be hacked. This is time consuming. BIND-VARS Function: bind-vars <pattern> <expression> <bindings> [Function] Variables are processed in <pattern> but treated as atoms in <expression>. <Bindings> should be existing bindings (usually nil). Dotted endings in <pattern> are assumed to be variables, and are processed. Returns two values: T or NIL to flag whether the pattern matches the expression, and a list of bindings which achieve this matching. BROWSE-DNETS Function: browse-dnets &optional <build-mode> [Function] Puts up a discrimination net browser. If <build-mode> is nil (default), the default button is for pattern retrieval; if T, the default is for adding an expression. DEFVARIABLE Function: defvariable <sym> [Macro] Interns the name of <sym> in the variable package ?, and exports it. Use to ensure the variable exists before using it in a pattern. For example, (defvariable x) lets us use ?:x as a variable in patterns. DELEXPR Function: delexpr <expr> <dnet> [Function] Deletes the expression <expr> from <dnet>, calling DELEXPR-HOOK if it is defined for the DNET. Returns a DNET-TERMINAL iff it was deleted. DESTROY-DNET Function: destroy-dnet <dnet> [Function] Destroys and undefines the entire <dnet>. DNET Function: DNET name &key :indexpr-hook :delexpr-hook :info-place) [Macro] Expands into CREATE-DNET call. The first argument is the name of the instance, and the remainder are optional keyword arguments for uncomputed slot values, using defaults if not given. DNET-COMPILED-DELEXPR-HOOK Exported but undocumented Function. DNET-COMPILED-INDEXPR-HOOK Exported but undocumented Function. DNET-DELEXPR-HOOK Exported but undocumented Function. DNET-INDEXPR-HOOK Exported but undocumented Function. DNET-INFO Function: dnet-info <dnet> [Macro] Setf-able access to the information associated with <dnet>. DNET-INFO-PLACE Exported but undocumented Function. DNET-TERMINAL-EXPR Exported but undocumented Function. DNET-TERMINAL-INFO Exported but undocumented Function. EXPR-INFO Function: expr-info <expr> <dnet> [Function] Setf-able access to the information associated with <expr> in <dnet>. GETEXPR Function: getexpr <expr> <dnet> [Function] Use to query whether <expr> has been stored in <dnet>, and to obtain the name of its dnet-terminal. Returns two values: the expression originally stored in <dnet> (and is EQUAL to <expr>), and the dnet-terminal structure. Both values are Nil if <expr> is not found. Variables are not processed. INDEXPR Function: indexpr <expr> <dnet> &optional <info> [Function] Ensures that <expr> is stored in <dnet>. If the <expr> was not already in <dnet>, initializes the associated information to <info> (if it was provided), and calls compiled-new-expr-hook (if non-nil) on <expr> and its dnet-terminal. The latter allows application-specific processing of new expressions. Returns two values: the first is a predicate, T iff <expr> was newly added by this call; and the second is the dnet-terminal structure. MAKE-DNET Function: make-dnet <name> &key <indexpr-hook> <delexpr-hook> <info> [Function] Returns a new (empty) discrimination net. A name is generated unless a symbol <name> is provided. <Indexpr-hook> and <delexpr-hook> are assumed to be lambda forms of two arguments which may be compiled. These functions are applied to an expression and its corresponding DNET-TERMINAL the first time it is indexed into or deleted from the DNET, respectively. If the optional <info> is provided, the DNET's associated information is initialized to this value. MAP-DNET-TERMINALS Function: map-dnet-terminals <f> <dnet> [Function] Maps <f> across dnet-terminals in the indicated <dnet>. Returns NIL. MATCH Function: match <pattern> <dnet> [Function] For retrieving all patterns unifying with a pattern: variables in both are processed. Returns three values: a list of all patterns in <dnet> unifying with the <pattern>, a list of bindings of variables in <pattern> to those in the matched patterns, and a list of bindings of variables in the matched patterns to those in <pattern>. The latter two values are lists of lists containing pairs (<var> . <exp>), each representing the binding of <var> to <exp> (ditto). Note this is less efficient than MATCH-PATTERN and MATCH-EXPRESSION, and should only be used when needed. See also documentation for UNIFY. MATCH-EXPRESSION Function: match-expression <expression> <dnet> [Function] For retrieving all patterns (which may contain variables) matching an expression. Returns two values: a list of all patterns in <dnet> matching the <expression>, and a list of respective unifications. The latter is a list of lists containing pairs (<exp-part> . <pat-var>) representing the binding of <pat-var> to <exp-part>, a component of <expression>. Variables in <expression> are treated as constants. MATCH-PATTERN Function: match-pattern <pattern> <dnet> [Function] For retrieving all expressions matching a pattern which may contain variables. Returns two values: a list of all expressions in <dnet> matching the <pattern>, and a list of respective unifications. The latter is a list of lists containing pairs (<pat-var> . <dnet-exp>) representing the binding of <pat-var> to <dnet-exp>, a component of the corresponding returned expression. Variables in the dnet are treated as constants. A special facility provided only by this function is dotted variables: any sublist of <pattern> may end in a dot followed by a variable. This is like &rest binding. NOT-A-DOTTED-LIST Function: not-a-dotted-list <expr> [Function] Returns T iff there is no non-nil atomic CDR in <expr>. PATTERN-P Function: pattern-p <expr> [Function] Returns non-NIL value iff <expr> is or contains a variable. RESET-DNET Function: reset-dnet <dnet> &key <indexpr-hook> <delexpr-hook> <info> [Function] Empties an existing discrimination net. Also enables one to modify the hooks and associated info. See MAKE-DNET. SAVE-DNET Function: save-dnet <dnet> <path> &optional (write-in-package :dnet) [Function] Saves expressions required to recreate <dnet> to a file at <path>. Returns the <path>. The file is written in package <write-in-package>, or DNET if the optional argument is unspecified. All associated info is also saved. Give <vars> a list of known variables. This function is slow. SUBSTITUTE-BINDINGS Function: substitute-bindings <bindings> <pattern> [Function] Given <bindings> is an association list as returned by one of the match functions, creates an expression from <pattern> where all the variables have been replaced by their bindings. New list structure is used. Only makes one pass -- see substitute-transitive-bindings if variables may be bound to each other. SUBSTITUTE-TRANSITIVE-BINDINGS Function: substitute-bindings <bindings> <pattern> [Function] Given <bindings> is an association list as returned by one of the match functions, creates an expression from <pattern> where all the variables have been replaced by their bindings. New list structure is used. Makes as many passes are needed to eliminate transitivities which may be returned by UNIFY when both patterns have variables, such as ((?:y . 3) (?:x . ?:y)) which unifies (?:x ?:x) and (?:y 3). UNIFY Function: unify <pattern-1> <pattern-2> &optional <bindings-1> <bindings-2> [Function] Given two list/atom patterns (each of which may contain variables), and a (usually nil) set of initial bindings, returns three values: 1. T or NIL to flag whether the patterns unify; 2. Bindings of variables in <pattern-1> to elements of <pattern-2>; 3. Bindings of variables in <pattern-2> to elements of <pattern-1>. (The flag is returned first so UNIFY can be used as a predicate. Since unification can succeed with no bindings, the other values will not serve this function.) Example: (unify '(a ?:x c) '(a (b) ?:y)) ==> T; ((?:X B)); ((?:Y . C)) Transitivity of bindings is not used for simplification, e.g. you could get back T; ((?:X . ?:Y)); ((?:Y . C)). Modified from version by Ken Forbus. This function is logically general, and hence checks for a variety of conditions. It may be inefficient for specialized tasks: I recommend writing a specialized version if any assumptions may be made about the patterns to be unified. VARIABLE-P Function: variable-p <thing> [Macro] Returns T iff <thing> is a variable (symbol in the ? package). VARIABLES-IN-PATTERN Function: variables-in-pattern <pattern> [Function] Returns a list of variables occuring in <pattern>. --------------------------------------------------------------------------- EXAMPLE --------------------------------------------------------------------------- ;;; Making a DNET called TEST. (dnet:make-dnet 'test) TEST ;;; Adding expressions to the DNET. INDEXPR returns two values: the first ;;; is T only if the expression is new to the DNET, and the second is the ;;; DNET-TERMINAL structure in which the expression is stored (this is ;;; returned for code which needs to efficiently access the terminal). (dnet:indexpr '(a b c) 'test) T #((A B C) NIL) (dnet:indexpr '(junk this one) 'test) T #((JUNK THIS ONE) NIL) ;;; Deletion is done by DELEXPR, which returns the DNET-TERMINAL object ;;; of the deleted expression (advanced code may need to operate on it), ;;; or NIL if the expression was not found to delete. (dnet:delexpr '(junk this one) 'test) #((JUNK THIS ONE) NIL) ;;; Let's add a few more expressions. (dnet:indexpr '(a (b) c) 'test) T #((A (B) C) NIL) (dnet:indexpr '(nil) 'test) T #((NIL) NIL) ;;; We find out if an expression is in the DNET by using GETEXPR. It returns ;;; two values. The first is the expression if found, or NIL if it is not ;;; found. The second value is the DNET-TERMINAL structure in which the ;;; expression is stored, provided for advanced code which needs efficient ;;; access to it: (dnet:getexpr '(a b c) 'test) (A B C) #((A B C) NIL) (dnet:getexpr '(junk this one) 'test) NIL NIL ;;; Variables are represented as atoms interned in the ? package. Before ;;; using a variable, we need to make sure it exists, as follows: (dnet:defvariable x) T ;;; Now we can see what things in the DNET match a given pattern: (dnet:match-pattern '(a ?:x c) 'test) ((A B C) (A (B) C)) ; two things match (((?:X . B)) ((?:X B))) ;;; MATCH-PATTERN returns two values: a list of all expressions which match ;;; the given pattern, and a list of the bindings which makes the match ;;; succeed. Both of these are NIL if there is no match. (dnet:match-pattern '(not there) 'test) NIL NIL ;;; We can also store patterns in the DNET, and match expressions to the ;;; DNET to find out what patterns in the DNET match the given expression. ;;; The returned values are similar: (dnet:defvariable y) T (dnet:indexpr '(a ?:x ?:y) 'test) T #((A ?:X ?:Y) NIL) (dnet:match-expression '(a b c) 'test) ((A B C) (A ?:X ?:Y)) ; again, two things match (NIL ((?:Y . C) (?:X . B))) ;;; See DNET-TEST and DNET-RULES for examples of other features of DNET. ;;; The file DNET-ANALYZE has a function which will report on the average ;;; and maximum depth and branching factor of a DNET, to help deal with ;;; efficiency problems. ===========================================================================